package com.saprk.demoarithmetic.leetcode;

/**
 * @author fuqiang
 * @Description 困难
 * @Date 2021-05-26
 */
public class Hard {

    /**
     * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
     * @author fuqiang
     * @date 2021-05-26 14:00
     * @param nums1
     * @param nums2
     * @return double
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {

        int length1 = nums1.length;
        int length2 = nums2.length;

        if(length1 == 0 && length2 != 0){
            return getMiddleNum(nums2);
        }
        if(length1 != 0 && length2 == 0){
            return getMiddleNum(nums1);
        }
        // 新建数组
        int[] newNum = new int[length1 + length2];
        // 获取较长的数组长度
        // 定义第一个数组的位置f , 第二个数组位置s
        int f = 0 , s = 0;
        for (int i = 0; i < length1 + length2; i++) {
            // num1数组排序结束 只剩下num2
            if(f == length1 && s < length2){
                newNum[i] = nums2[s];
                s++;
                continue;
            }
            // num2数组排序结束 只剩下num1
            if(f < length1 && s == length2){
                newNum[i] = nums1[f];
                f++;
                continue;
            }
            // nums1 nums2 都结束
            if(f == length1 && s == length2){
                continue;
            }
            // 把数值最小的放到新数组中
            if(nums1[f] >= nums2[s]){
                newNum[i] = nums2[s];
                s++;
            }else{
                newNum[i] = nums1[f];
                f++;
            }
        }
        return getMiddleNum(newNum);
    }
    /**
     * 获取中位数
     * @author fuqiang
     * @date 2021-05-26 15:12
     * @param num
     * @return double
     */
    public static double getMiddleNum(int[] num){

        int length = num.length ;

        if(length == 0){
            return 0;
        }

        if(length % 2 == 1){
            return num[length/2];
        }else{
            return (num[length/2] + num[length/2-1]) / 2d;
        }
    }


    public static void main(String[] args) {
        int[] num1 = {1,2,4,6};
        int[] num2 = {1,3,5,11,68,88};
        int[] num3 = {1,1,2,4,5,6,11,68,88};

//        double middleNum = getMiddleNum(num3);
        double medianSortedArrays = findMedianSortedArrays(num1, num2);
        System.out.println(medianSortedArrays);
    }

}
